package com.yitiao.data_algorithms.algorithms;

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.locks.ReentrantLock;

/**
 * Reports fields that can be safely made final. All final fields have a value and this value does not change, which can make the code easier to reason about.
 * To avoid too expensive analysis, this inspection only reports if the field has a private modifier or it is defined in a local or anonymous class.
 * A field can be final if:
 * It is static and initialized once in its declaration or in one static initializer.
 * It is non-static and initialized once in its declaration, in one instance initializer or in every constructor
 * And it is not modified anywhere else.
 * Example:
 *   public class Person {
 *     private String name; // can be final
 *
 *     Person(String name) {
 *       this.name = name;
 *     }
 *
 *     public String getName() {
 *       return name;
 *     }
 *   }
 * After the quick-fix is applied:
 *   public class Person {
 *     private final String name;
 *
 *     Person(String name) {
 *       this.name = name;
 *     }
 *
 *     public String getName() {
 *       return name;
 *     }
 *   }
 */
public class SafeLRUCache {
    private final int capacity;
    private final ConcurrentHashMap<Integer, Node> map;
    private final ReentrantLock lock = new ReentrantLock();

    /**
     * 证最近访问的节点在链表头部。
     * 同时，当缓存满时，需要移除链表尾部的节点。
     */
    private static class Node {
        int key;
        int value;
        Node prev;
        Node next;
        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    private final Node head;
    private final Node tail;

    public SafeLRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new ConcurrentHashMap<>();
        this.head = new Node(-1, -1);
        this.tail = new Node(-1, -1);
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }

    public int get(int key) {
        Node node = map.get(key);
        if (node == null) {
            return -1;
        }
        lock.lock();
        try {
            remove(node);
            addFirst(node);
        } finally {
            lock.unlock();
        }
        return node.value;
    }

    public void put(int key, int value) {
        Node node = map.get(key);
        if (node != null) {
            lock.lock();
            try {
                node.value = value;
                remove(node);
                addFirst(node);
            } finally {
                lock.unlock();
            }
        } else {
            node = new Node(key, value);
            lock.lock();
            try {
                if (map.size() == capacity) {
                    Node last = tail.prev;
                    remove(last);
                    map.remove(last.key);
                }
                map.put(key, node);
                addFirst(node);
            } finally {
                lock.unlock();
            }
        }
    }
    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    private void addFirst(Node node) {
        Node next = head.next;
        head.next = node;
        node.prev = head;
        node.next = next;
        next.prev = node;
    }


}
